1. Field of the Invention
The methods, devices, and systems described herein generally relate to channel decoding.
2. Description of the Related Art
Channel coding or forward error correction coding (FEC) consists of adding redundancy to information data to be sent over a noisy channel or stored on a medium which is likely to be damaged, such as a CD-ROM. Whether receiving or reading, redundant data can allow recovering the information data.
With reference to FIG. 1, a typical generic transmission subsystem contains, on the side of the transmitter 10, a data source 11 (DAT_SRC), followed by a source encoder 12 (SCR_ENC), a channel encoder 13 (CH_ENC), and a modulator 14 (MOD). The source encoder 12 compresses the information data (for example, using a standard such as MPEG, H264, etc.) so as to reduce the amount of data to be transmitted. The channel encoder 13 adds redundancy to enable the receiver 30 to correct potential errors due to the noise N introduced into the transmission channel 20. The modulator 14 adapts the signal to the transmission channel (for example, satellite transmission channel, radio transmission channel, etc.). On the receiver side 30, a demodulator 34 (DEMOD) followed by a channel decoder 33 (CH_DEC) and a source decoder 32 (SRC_DEC), perform operations inverse to those performed by the modulator 14, the channel encoder 13, and the source encoder 12, respectively. The demodulated and decoded data are then restored to the entity that uses the data 31 (DAT_U).
Block codes, among the current most common error correcting codes, consist of adding to each message of K information bits a given number (N-K) of redundancy bits, so as to form codewords of N bits.
Examples of block-based channel coding algorithms include the BCH (Bose-Chaudhuri-Hocquenghem) code, the Reed-Solomon codes, the Hamming code, and the LDPC (Low Density Parity Check) codes.
BCH and Reed-Solomon error correcting codes are part of a class of codes which are described through the roots of a polynomial with coefficients in a finite field called the Galois field.
With such codes, data are received at a receiver, with these data corresponding to the codewords sent over a channel. For a bit d of a sent codeword which has a corresponding received signal y, a decision is made, after steps of demodulation and synchronization, to associate a binary value to this signal y. Because of noise in the channel, the bit value associated with a signal y may be erroneous.
The error detection means enable detecting errors from the received bit values. The error detection means may comprise syndrome calculation means, error locator polynomial coefficient determination means, and error position locator means.
A number 2t of syndrome components are calculated from the bit values received, with t corresponding to the maximum number of errors which may be corrected per block. If all the components are zero, this means the transmission was performed without errors or that the addition of channel noise to the transmitted codeword has produced a new codeword.
Otherwise, the calculated components are processed to locate the positions of errors via an error locator polynomial. The positions of erroneous bits are obtained by determining the roots of the error locator polynomial.
FIG. 2 schematically shows an example of a device for decoding data corresponding to codewords obtained by prior art BCH coding.
The bit values are received one by one by the syndrome calculation means 21. The component values thus calculated are sent to the error locator polynomial coefficient determination means 22 based on the syndrome components. The coefficients are then sent to the error locator means 23 based on the error locator polynomial.
In the case of decoding with a Reed-Solomon algorithm, an additional step using the Forney algorithm may be applied prior to the correction step.
The correction means, for example an adder 25, enable modifying the received bit values corresponding to the positions of the located errors. The error position locator means 23 can send a vector of K serial bits to the adder. The bits of this vector are zero except for the bits situated at the positions of the located errors.
The received bits are temporarily stored in a buffer 24, for example a FIFO (First In First Out) buffer. The received bits remain in the FIFO buffer for the time necessary to calculate the syndrome and determine the error positions.
LDPC codes are a class of error correcting codes invented in 1960 by Robert Gallager, which constitute an alternative to the Viterbi codes as well as to the more recent turbo codes. The first commercial standard stipulating the use of an LDPC code is the DVB-S2 standard, which is the second-generation ETSI (European Telecommunication Standardization Institute) standard for satellite digital video broadcasting. The DVB-S2 standard, published by ETSI, is incorporated herein in its entirety.
An LDPC encoder adds N-K redundancy bits to a message of K bits, which enable correcting transmission errors on the receiver side. These N-K bits are called parity bits.
The N-K bits added to each message of K information bits are calculated using an H matrix called the parity check matrix. This H matrix has N-K rows and N columns. It contains “0” and “1” values, with the latter in low proportions, which is why codes based on such a parity matrix are called low density parity check codes. The H matrix may, for example, contain 48600 rows and 64800 columns, meaning K=16200 and N=64800.
On the receiver side, the LDPC decoder corrects erroneous bits based on the blocks received through the transmission channel. Each block corresponds to a codeword sent over the transmission channel. For each bit sent there is a corresponding log-likehood ratio (LLR). Each LLR is coded in a number m of bits, for example 6 bits.
A block therefore comprises N*m bits, for example 64800*6 bits.
For a bit d which has a corresponding signal y received by the LDPC decoder after noise is added to the transmission channel, the LLR ratio for the bit d in relation to the signal y is defined as:
      LLR    ⁡          (      y      )        =            LLR      ⁡              (                  d          /          y                )              =          ln      ⁢                          ⁢                        P          ⁡                      (                          d              =                              0                /                y                                      )                                    P          ⁡                      (                          d              =                              1                /                y                                      )                              where P(d=0/y) is the probability that the sent bit d is equal to 0 as a function of the received value y, and P(d=1/y) is the probability that the sent bit d is equal to 1 as a function of the received value y.
The LDPC decoder uses internal metrics, equal in number to the number of “1” values in the H matrix, and each coded in a number t of bits. The decoder updates these metrics using an iterative algorithm.
To decode an LDPC block received in order to recover a block of N data sent, the decoder performs multiple iterations, for example about fifty iterations. Each internal metric converges towards a given value.
The decoded bits, called hard decision bits, are then obtained by adding the internal metrics by column with the LLRs received. In a decision step, the sign of the sum allows determining the value of the decoded bit.
With reference to FIG. 3, the typical architecture of a prior art LDPC decoder comprises an input memory or channel memory 41 (denoted CH_MEM in the figure), capable of storing a number 2×N of LLRs. More particularly, the memory 41 comprises a first storage element 41a for storing the N LLRs of the previously received block which is currently being decoded, and a second storage element 41b for storing the N LLRs of a block currently being received.
The decoder also comprises processing means. In order to accelerate the calculations related to decoding, said processing means comprise a methodor bank 42. These P methodors (denoted Proc1 to ProcP in FIG. 3) perform in parallel the update calculations by row and by column. The number P is called the parallelism index.
During execution of the iterative method, the methodors deliver updated values of internal metrics, each coded in t bits. The internal metrics are stored in a metric memory 43 (denoted MET_MEM in FIG. 3). The internal metrics stored in the memory 43 are delivered to the methodor bank 42 via a P-channel mixer, such as a barrel shifter 44 (denoted BS in FIG. 3) in the case of the DVB-S2 standard. The memory 43 is read and write accessible via respective buses of t×P wires.
During the last iteration, the methodors 42 also deliver K or N hard decision bits, which assume the values “1” or “0” depending on the sign of the sum of the columns of the H matrix and the corresponding LLRs. This set of K or N hard decision bits is stored temporarily in an output memory, or hard decision memory 45 (denoted HD_MEM in FIG. 3). The methodor bank 42 can write to the hard decision memory 45 via a bus of P wires.
The double encoding of information bits in order to better protect against noise is already known. FIG. 4 shows an example of such a concatenation. The channel encoder 53 adds redundancy on the side of the transmitter 10 to enable the receiver 30 to correct potential errors due to the noise N introduced into the transmission channel 20. For example, K1 information bits are first encoded using a BCH encoding algorithm. The N1 BCH encoded bits constitute the K2 bits to be encoded using an LDPC algorithm. N2-N1 redundancy bits are thus added to the N1 BCH encoded bits. N2 encoded bits are then obtained.
The channel encoder 53 comprises a BCH encoding device 51 and an LDPC encoding device 52.
Upon receipt, the received signals are converted into LLRs then decoded using the LDPC decoding algorithm corresponding to the LDPC encoding performed. The bits decoded using the LDPC decoding algorithm are then decoded using a BCH decoding algorithm corresponding to the BCH encoding performed. The channel decoding device 54, on the side of the receiver 30, comprises an LDPC decoding device 56 and a BCH decoding device 57.
The LDPC decoding device may, for example, comprise an LDPC decoder such as the one represented in FIG. 3.
The BCH decoding device may comprise a decoding device such as the one represented in FIG. 2.
The LDPC decoder presents a parallelism index P, for example 360, for accelerating the processing of the LLRs. Therefore P hard decision bits are written simultaneously to the hard decision memory. K2/P write cycles are thus necessary to write the K2 LDPC decoded bits to the hard decision memory. These K2 LDPC decoded bits, or in other words the N1 BCH encoded bits, are next sent sequentially to the error detection means, then to the correction means for the BCH decoding device.
It is possible to replace the hard decision memory 45 in FIG. 3 and the FIFO buffer 24 in FIG. 2 with a single intermediate buffer which receives the hard decision bits from the methodor bank P and sequentially sends the N1 bits to the error detection means then to the correction means.
FIG. 5 shows an example of timing diagrams for a decoding device with a single intermediate buffer. The first timing diagram corresponds to the sets of N2 bits processed by the LDPC decoder. The second timing diagram corresponds to the sets processed by the error detection means of a BCH decoding device. The third timing diagram corresponds to the sets processed by the correction means of the BCH decoding device.
In these timing diagrams the latency from calculating the error locator polynomial is considered to be negligible.
A first set is processed by the P methodors of the LDPC decoder until time t1. The LDPC_p variable is an index which assumes the values of whole numbers indicating which set the LDPC decoder is currently processing.
Between time t0 and time t1, K2 (or N1) hard decision bits are written to the intermediate buffer during the last LDPC iteration. These K2 bits are sent sequentially to the error detection means and processed between times t1 and t2. The BCH_p variable indicates which set of K2 bits the error detection means are currently processing.
Between times t2 and t3, the erroneous bits are corrected. The BCH_output variable indicates which set the correction means are currently processing. The correction means perform bitwise addition of a vector output from the error detection means and K1 hard decision bits corresponding to the K1 BCH information bits. The intermediate buffer must send the K1 hard decision bits one at a time to the correction means between times t2 and t3. The intermediate buffer therefore cannot receive new hard decision bits corresponding to a new set before time t3. The number K1 of BCH information bits may be relatively close to N1, such that the duration between times t2 and t3 may be relatively close to the duration between times t1 and t2.
With existing LDPC and BCH decoding devices, the decoding step using the BCH algorithm may well limit the bit rate of the LDPC decoding.
It is known to use two buffers rather than a single intermediate buffer. The N1 hard decision bits may be stored in either buffer.
FIG. 6 shows examples of timing diagrams for a decoding device with two buffers. The variables MEM_1 and MEM_2 respectively indicate which set of N1 bits is stored in the first buffer and second buffer over time.
As before, the latency from calculating the error locator polynomial is considered to be negligible.
At time t0, a set, corresponding to an index with a value of 0, is processed by the LDPC decoder and N1 hard decision bits are written to the first buffer. As described above, the first buffer must sequentially send these N1 bits to the error detection means in order to be processed between times t0 and t1. The first buffer must then sequentially send K1 bits of the stored N1 bits to the correction means between times t1 and t2. The correction means in fact use data generated by the error detection means based on the same hard decision bits. The first buffer is therefore not available for a new set before time t2. The number K1 of BCH information bits may be relatively close to N1, such that the duration between times t1 and t2 may be relatively close to the duration between times t0 and t1.
However, a new set of N1 hard decision bits may be decoded and written to the second memory at time t1. Even if the latency is approximately two sets, the error detection means are more regularly used than in the device with a single intermediate buffer.
With existing decoding devices, it is the LDPC decoder here which limits the bit rate for the decoded data.